package letcode.problem.dynamicProgra;

/**
 * https://leetcode.cn/problems/unique-paths/solutions/5772/dong-tai-gui-hua-by-powcai-2/?envType=study-plan-v2&envId=dynamic-programming
 * */
public class UniquePath {
    public static int uniquePath(int m, int n) {

        int[][] memo = new int[m+1][n+1];
        return uniquePathMemo(memo, m, n);
    }

    //自顶而下
    public static int uniquePathMemo(int[][] memo, int m, int n) {
        if (memo[m][n] > 0) {
            return memo[m][n];
        }
        if (m < 1 || n < 1) {
            return 0;
        }
        if (m == 1 && n == 1) {
            memo[m][n] = 1;
            return 1;
        }
        if (m == 1 && n == 2) {
            memo[m][n] = 1;
            return 1;
        }
        if (m == 2 && n == 1) {
            memo[m][n] = 1;
            return 1;
        }
        memo[m][n] = uniquePathMemo(memo, m - 1, n) + uniquePathMemo(memo, m, n - 1);
        return  memo[m][n];
    }

    //自底而上
    public int dpUniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < n; i++) dp[0][i] = 1;
        for (int i = 0; i < m; i++) dp[i][0] = 1;
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }

    public static void main(String[] args) {
        System.out.println(
                uniquePath(51, 9)
        );
    }
}
